package com.hjj.dataStructures.linkedList;

import java.sql.Statement;
import java.util.Stack;

/**
 * @author hjj
 * @create 2019-11-16 20:05
 */
public class SingleLinkedListDemo {
    public static void main(String[] args) {
        HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
        HeroNode hero4 = new HeroNode(4, "公孙胜", "入云龙");
        HeroNode hero5 = new HeroNode(5, "关胜", "大刀");
        HeroNode hero6 = new HeroNode(6, "林冲", "豹子头");
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        // 添加
//        singleLinkedList.add(hero6);
//        singleLinkedList.add(hero5);
//        singleLinkedList.add(hero3);
//        singleLinkedList.add(hero4);
//        singleLinkedList.add(hero1);
//        singleLinkedList.add(hero2);
        // 按编号顺序添加
        singleLinkedList.addByOrder(hero6);
        singleLinkedList.addByOrder(hero5);
        singleLinkedList.addByOrder(hero3);
        singleLinkedList.addByOrder(hero4);
        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero2);
        singleLinkedList.addByOrder(hero2);
        singleLinkedList.list();
        // 测试修改节点的代码
        HeroNode newHeroNode = new HeroNode(2, "小卢", "玉麒麟~~~");
        singleLinkedList.update(newHeroNode);
        System.out.println("=======修改之后的链表");
        singleLinkedList.list();

        int length = singleLinkedList.getLength(singleLinkedList.getHead());
        System.out.printf("有效节点个数为：%d\n", length);
        // 删除节点
        singleLinkedList.delete(5);
        singleLinkedList.delete(6);
        singleLinkedList.delete(1);
        singleLinkedList.delete(0);
        System.out.println("=======删除节点之后");
        singleLinkedList.list();
        length = singleLinkedList.getLength(singleLinkedList.getHead());
        // 测试单链表的有效节点个数
        System.out.printf("有效节点个数为：%d\n", length);
        // 测试获取到第k个倒数节点
        System.out.println("获取到倒数第二个节点：" + singleLinkedList.getLastIndexNode(singleLinkedList.getHead(), 2));
        // 测试单链表的反转
        singleLinkedList.reverseList(singleLinkedList.getHead());
        System.out.println("======反转之后的单链表");
        singleLinkedList.list();
        // 测试逆序打印链表
        System.out.println("======测试逆序打印链表");
        singleLinkedList.reversePrint(singleLinkedList.getHead());
        System.out.println("======链表本身没有变化");
        singleLinkedList.list();
    }

}

class SingleLinkedList {
    // 先初始化一个头节点，头节点不要动，不存放具体的数据
    private HeroNode head = new HeroNode(0, "", "");

    // 返回头节点
    public HeroNode getHead() {
        return head;
    }

    // 添加节点到单向链表
    // 当不考虑编号顺序时
    // 1 找到当前链表的最后节点
    // 2 将最后这个节点的next指向新的节点
    public void add(HeroNode heroNode) {
        HeroNode temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = heroNode;

        // 因为head节点不能动，因此我们需要一个辅助遍历temp
//        HeroNode temp = head;
        // 遍历链表，找到最后
//        while (true) {
//            // 找到链表的最后
//            if (temp.next == null) {
//                break;
//            }
//            // 如果没有找到最后，将temp后移
//            temp = temp.next;
//        }
        // 当退出while循环时，temp就指向了链表的最后
//        temp.next = heroNode;
    }

    // 在添加英雄时，根据排名将英雄插入到指定位置
    // (如果有这个排名，则添加失败，并给出提示)
    public void addByOrder(HeroNode heroNode) {
        // 因为头节点不能动，因此通过一个辅助（变量）来帮助添加的位置
        // 因为单链表，故temp是位于添加位置的前一个节点，否则插入不了
        HeroNode temp = head;
        boolean flag = false; // 标志添加的编号是否存在，默认为false
        while (true) {
            if (temp.next == null) { // 说明temp已经在链表的最后
                break;
            }
            if (temp.next.getNo() > heroNode.getNo()) { // 位置找到，就在temp的后面插入
                break;
            } else if (temp.next.getNo() == heroNode.getNo()) {
                flag = true;
                break;
            }
            temp = temp.next; // 后移，遍历当前链表
        }
        // 判断flag的值
        if (flag) { // 不能添加，说明编号已经存在
            System.out.printf("准备添加的英雄的编号%d已经存在了，不能加入\n", heroNode.getNo());
        } else {
            // 插入到链表中，temp的后面
            // 新的节点.next = temp.next
            heroNode.next = temp.next;
            // temp.next = 新的节点
            temp.next = heroNode;
        }
    }

    // 修改节点的信息，根据no编号来修改，即no编号不能修改
    public void update(HeroNode newHeroNode) {
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        // 找到需要修改的节点，并修改对应节点的值
        HeroNode temp = head.next;
        boolean flag = false;
        while (temp != null) {
            if (temp.getNo() == newHeroNode.getNo()) {
                flag = true;
                temp.setName(newHeroNode.getName());
                temp.setNickName(newHeroNode.getNickName());
                break;
            }
            temp = temp.next;
        }
        if (!flag) System.out.printf("没有找到编号为%d的节点，不能修改\n", newHeroNode.getNo());

        // 判断是否为空
//        if (head.next == null) {
//            System.out.println("链表为空");
//            return;
//        }
        // 找到需要修改的节点,根据no
//        HeroNode temp = head.next;
//        boolean flag = false;
//        while (true) {
//            if (temp == null) {
//                break;
//            }
//            if (temp.getNo() == newHeroNode.getNo()) {
//                flag = true;
//                break;
//            }
//            temp = temp.next;
//        }
//        if (flag) {
//            temp.setName(newHeroNode.getName());
//            temp.setNickName(newHeroNode.getNickName());
//        } else {
//            System.out.printf("没有找到编号为%d的节点，不能修改\n", newHeroNode.getNo());
//        }
    }

    /**
     * 获取到单向链表的节点个数（如果带头节点的链表，需要不统计头节点）
     *
     * @param head 链表的头节点
     * @return 有效节点的个数
     */
    public int getLength(HeroNode head) {
        if (head.next == null) return 0;
        int length = 0;
        // 定义一个辅助的变量，这里没有统计头节点
        HeroNode currentNode = head.next;
        while (currentNode != null) {
            length++;
            currentNode = currentNode.next;
        }
        return length;
    }

    // 删除节点
    // 1 head不能动，需要一个temp辅助节点找到待删除节点的前一个节点
    // 2 在比较时，是temp.next.no和需要删除的节点的no比较
    public void delete(int no) {
        HeroNode temp = head;
        boolean flag = false;
        while (temp.next != null) {
            if (temp.next.getNo() == no){
                flag = true;
                temp.next = temp.next.next;
                break;
            }
            temp = temp.next;
        }
        if (!flag) System.out.printf("要删除的%d节点不存在\n", no);


//        HeroNode temp = head;
//        boolean flag = false;
//        while (true) {
//            if (temp.next == null) {
//                break;
//            }
//            if (temp.next.getNo() == no) {
//                flag = true;
//                break;
//            }
//            temp = temp.next;
//        }
//        if (flag) {
//            temp.next = temp.next.next;
//        } else {
//            System.out.printf("要删除的%d节点不存在\n", no);
//        }
    }

    // 显示链表
    public void list() {
        // 判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        // 因为头节点，不能动，因此需要一个辅助变量来遍历
        HeroNode temp = head.next;
        while (temp != null) {
            System.out.println(temp);
            temp = temp.next;
        }
//        while (true) {
//            // 判断是否到链表最后
//            if (temp == null) break;
//            // 输出节点信息
//            System.out.println(temp);
//            // 将temp后移
//            temp = temp.next;
//        }
    }

    // 查找链表中的倒数第k个节点【新浪面试题】
    // 思路：
    // 1 编写一个方法，接收head节点，同时接收一个index
    // 2 index表示是倒数第index个节点
    // 3 先把链表遍历，得到链表的总的长度 getLength
    // 4 得到size后，从链表的第一个开始遍历（size-index）个，就可以得到
    public HeroNode getLastIndexNode(HeroNode head, int index) {
        if (head.next == null) return null;
        // 第一个遍历得到链表的长度（节点个数）
        int length = getLength(head);
        // 先做index的校验
        if (index <= 0 || index > length) {
            return null;
        }
//        int count = 0;
//        HeroNode temp = head.next;
//        while (true) {
//            if (count == (length - index)) break;
//            temp = temp.next;
//            count++;
//        }
        HeroNode currentNode = head.next;
        for (int i = 0; i < length - index; i++) {
            currentNode = currentNode.next;
        }
        return currentNode;
    }

    /**
     * 反转链表
     * 1 先定义一个节点，reverseHead = new HeroNode();
     * 2 从头到尾遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead的最前端
     * 3 原来的链表的 head.next=reverseHead.next
     *
     * @param head
     * @return
     */
    public void reverseList(HeroNode head) {
        if (head.next == null || head.next.next == null) return;
        // 定义一个辅助的指针（变量），帮组遍历原来的链表
        HeroNode currentNode = head.next;
        HeroNode next = null; // 指向当前节点的下一个节点
        HeroNode reverseHead = new HeroNode(0, "", "");
        // 遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead的最前端
        while (currentNode != null) {
            next = currentNode.next; // 先暂时保存当前节点的下一个节点，因为后面需要使用
            currentNode.next = reverseHead.next; // 将currentNode的下一个节点指向新的链表的最前端
            reverseHead.next = currentNode; // 将currentNode连接到新的链表上
            currentNode = next; // 让currentNode后移
        }
        // 将head.next指向reverseHead.next，实现单链表的反转
        head.next = reverseHead.next;
    }

    // 可利用栈，将各个节点压入到栈中，然后利用栈的先进后出的特点，就可实现逆序打印的效果
    public void reversePrint(HeroNode head) {
        if (head.next == null) return;
        // 创建一个Stack，将各个节点压入栈中
        Stack<HeroNode> stack = new Stack<>();
        HeroNode currentNode = head.next;
        // 将链表所有的节点压入栈
        while (currentNode != null) {
            stack.push(currentNode);
            currentNode = currentNode.next;
        }
        // 将栈中的节点进行打印，pop
        while (stack.size() > 0) {
            System.out.println(stack.pop());
        }
    }
}

// 定义HeroNode，每个HeroNode，对象就是一个节点
class HeroNode {
    private int no;
    private String name;
    private String nickName;
    public HeroNode next; // 指向下一个节点

    public HeroNode(int no, String name, String nickName) {
        this.no = no;
        this.name = name;
        this.nickName = nickName;
    }

    public int getNo() {
        return no;
    }

    public String getName() {
        return name;
    }

    public String getNickName() {
        return nickName;
    }

    public void setName(String name) {
        this.name = name;
    }

    public void setNickName(String nickName) {
        this.nickName = nickName;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '\'' +
//                ", next=" + next +
                '}';
    }
}
